There are numerous circumstances in which it is useful to determine if a specified path is blocked by a specified obstacle. For example, in robotics, the system may need to find a clear path through a known terrain to a specified destination. This would apply equally well to a fixed position robot with a moveable arm as to a moveable robot.
Other applications include checking an airplane's proposed trajectory against a known terrain and/or set of obstacles, and hidden line calculations for video display systems.
The present invention provides a fast solution to the question: does a given line in space intersect a given volume? Alternately, the invention can be used to generate a representation of the relationship between two points and a given volume, thereby providing data for selecting one of a number of possible subsequent calculations.
In the prior art known to the inventor, path blockage analysis requires a series of mathematical calculations performed by a computer using an algorithm specified by a computer program. In both two and three dimensional situations this requires numerous computer clock cycles.
In the present invention, the processing time required for three dimensional path analyses is the same as for two dimensional analyses. What differs is the amount of hardware needed. In the prior art, the time required for three dimensional analyses increases exponentially with the number of dimensions. Thus the higher the dimension of the path analyses, the greater the advantage provided by this invention.
The present invention analyzes the relationship between a path and an obstacle (also referred to as an object) by performing a set of comparisons without performing any mathematical calculations. By performing this analysis using dedicated hardware to simultaneously perform the comparisons, and also to decode the results of the comparisons, instead of performing a series of calculations in a computer, the amount of time required to perform the analysis can be substantially reduced.
In some circumstances, the result of the initial comparison analysis performed by the invention will be ambiguous--i.e., the result of the analysis will be that the specified path may or may not be blocked by the specified object. Sometimes the ambiguous result will be all that is needed. For instance, a system incorporating the invention may be looking at several possible paths and will select the first unambiguously clear path. In some circumstances a system incorporating the invention might reject clearly blocked paths but accept paths which involve some risk of being blocked.
In some embodiments of the invention, the system will resolve ambiguities resulting from the initial path analysis by performing a set of calculations which eliminate the ambiguity. The information resulting from the initial path analysis is used to determine the calculations needed to resolve the ambiguity, thereby reducing the number of calculations needed to determine if the specified object blocks the specified path.
It is therefore a primary object of the present invention to provide a path blockage analysis system and method which performs its analysis substantially faster than it would take a conventional computer to perform the same analysis.
Another object of the present invention is to provide a path blockage analysis system which simultaneously performs a set of predefined comparisons to determine the relationship between a specified path and a given obstacle.